#include "kl.h"

KL::KL(Grafo *grf, int tot, double fB){
  
  grafo = grf;
  total = tot;
  
  n = grafo->adj.size();
  
  fatorBalanceamento = fB;

  pesoParticao[0] = 0;
  pesoParticao[1] = 0;

  particao = grafo->pOtima;
  
  preencheGanhoMax();

  //printf("Ganho OK\n");

  custo = (int *) malloc(sizeof(int) * n);

  bucket[0] = (cell *) malloc(sizeof(cell) * (2*gmax + 1));
  bucket[1] = (cell *) malloc(sizeof(cell) * (2*gmax + 1));

  topo[0] = 0;
  topo[1] = 0;

  for(int i = 0; i < 2*gmax + 1; ++i){

    bucket[0][i].no = -1;
    bucket[0][i].ant = &bucket[0][i];
    bucket[0][i].prox = &bucket[0][i];

    bucket[1][i].no = -1;
    bucket[1][i].ant = &bucket[1][i];
    bucket[1][i].prox = &bucket[1][i];
  }
  
  pt = (cell**) malloc(n * sizeof(cell *));

  for(int i = 0; i < n; i++) pt[i] = NULL;
  
  preenchePesoParticao();
  
  particao_otima = (int *) malloc(sizeof(int) * (n + 1));
	
  //printf("\nInicializacao OK\n");

  preencheBuckets();

//	printf("Buckets OK\n");

  atribuiParticaoOtima();

//	printf("Particao Otima OK\n");

  refina();
}

void KL::atribuiParticaoOtima(void){
  
  for(int i = 0; i <= n; ++ i){
    particao_otima[i] = particao[i];
  }
  
}

void KL::preenchePesoParticao(void){

  for(int i = 0; i < n; ++i){
    pesoParticao[particao[i]] += grafo->vPeso[i];
  }

  //printf("Inicio ----- PesoA = %d, pesoB = %d\n", pesoParticao[0], pesoParticao[1]);

}

void KL::preencheGanhoMax(void){

  int g;

  gmax = 0;

  for(int i = 0; i < n; ++i){

    g = 0;

    for(unsigned int j = 0; j < grafo->adj[i].size(); ++j){

      g+= grafo->adj[i][j].peso;
    }

    if(g > gmax) gmax = g;

  }
}


void KL::preencheBuckets(void){

  //computa ganho das celulas e custo da partição e insere nos buckets

  particao[n] = 0;

  for(int i = 0; i < n; ++ i){

    int g = 0;

    for(unsigned int j = 0; j < grafo->adj[i].size(); ++j){

      if(particao[grafo->adj[i][j].v] != particao[i]){ 
	g += grafo->adj[i][j].peso;
	particao[n] += grafo->adj[i][j].peso;
      }
      else g -= grafo->adj[i][j].peso;
    }

    insere(i, g, particao[i]);
  }
  
  particao[n] = particao[n]/2;

  printf("KL::Custo corte: %d\n", particao[n]);
}

void KL::insere(int no, int ganho, int p) {

  cell *nova_celula = (cell*) malloc(sizeof(cell));

  nova_celula->no = no;
  custo[no] = ganho;  

  nova_celula->ant = bucket[p][ganho + gmax].ant;
  
  bucket[p][ganho + gmax].ant->prox = nova_celula;
  
  nova_celula->prox = &bucket[p][ganho + gmax];

  bucket[p][ganho + gmax].ant = nova_celula;
  
  pt[no] = nova_celula;

  if(topo[p] < ganho + gmax) topo[p] = ganho + gmax;

}

cell* KL::melhor(int p) {
  return bucket[p][topo[p]].prox;
}

void KL::remove_melhor(int p){

  if(bucket[p][topo[p]].prox == &bucket[p][topo[p]]) return;
  //bucket tah vazio
	
  cell* melhor = bucket[p][topo[p]].prox;
	
  //Conserta a vizinhança
  for(unsigned int j = 0; j < grafo->adj[melhor->no].size(); ++j){

     if(particao[melhor->no] == particao[grafo->adj[melhor->no][j].v]){	//alterar para trabalhar com peso
       
       particao[n] -= grafo->adj[melhor->no][j].peso;
       custo[grafo->adj[melhor->no][j].v] -= (2 * grafo->adj[melhor->no][j].peso);
     
     }else{
       
       particao[n] += grafo->adj[melhor->no][j].peso;
       custo[grafo->adj[melhor->no][j].v] += (2 * grafo->adj[melhor->no][j].peso);

     }
     
     if(pt[grafo->adj[melhor->no][j].v] == NULL) continue;
     
     remove(grafo->adj[melhor->no][j].v);
     insere(grafo->adj[melhor->no][j].v, custo[grafo->adj[melhor->no][j].v], particao[grafo->adj[melhor->no][j].v]);
  }
  
  remove(melhor->no);

  //Conserta o topo
  for(int p = 0; p < 2; ++p){

    while(topo[p] > 0 && 
    bucket[p][topo[p]].prox == &bucket[p][topo[p]])topo[p]--;
  }
}

void KL::remove(int no){

  if(pt[no] == NULL) return;

  cell* ptn = pt[no];

  ptn->ant->prox = ptn->prox;
  ptn->prox->ant = ptn->ant;

  free(ptn);

  pt[no] = NULL;
}


void KL::refina(void){

  cell *otm;

  for(int i = 0; i < n/2; ++i){

    for(int p = 0; p < 2; ++p){
      
      //pega o melhor
      otm = melhor(p);
      //printf("melhor da P%d: %d\n", p, otm->no);

      if(otm->no == -1) break;

      //troca de particao
      particao[otm->no] = (p +1)%2;
      pesoParticao[p] -= grafo->vPeso[otm->no];
      pesoParticao[(p +1)%2] += grafo->vPeso[otm->no];
      
      //remove e atualiza
      remove_melhor(p);
      
      /*--------------------------
      for(int z = 0; z < n; ++z){
	printf("%d ", particao[z]);
      }
      printf("\nCusto : %d\n\n", particao[n]);
      */
      
      if(pesoParticao[0] <= ceil(fatorBalanceamento * total) &&
	pesoParticao[1] <= ceil(fatorBalanceamento * total) &&
	particao[n] < particao_otima[n])
	  atribuiParticaoOtima();
    }
  }
  
  grafo->pOtima = particao_otima;
}

